面试题 17.14. 最小 K 个数

LeetCode：原题
难度：中等
归类：数组、分治、快速选择、排序、堆（优先队列）
主解法：快速选择

题目描述

设计一个算法，找出数组中最小的 k 个数，并以任意顺序返回。

输入：arr = [1,3,5,7,2,4,6,8], k = 4
输出：[1,2,3,4]

输出不要求有序，因此 [1,3,2,4] 也是合法答案。

题目保证：

0 <= arr.length <= 100000
0 <= k <= min(100000, arr.length)

核心思路

如果先对整个数组排序，再取前 k 个数，时间复杂度是 O(n log n)。但题目只关心最小的 k 个数，并不要求这 k 个数内部有序，因此没有必要完成全部排序。

快速选择借用了快速排序的分区思想：

选取一个基准值 pivot。
把当前区间分为“小于 pivot”“等于 pivot”“大于 pivot”三段。
判断目标下标 k - 1 落在哪一段。
只继续处理包含目标下标的那一侧，另一侧可以直接排除。

当目标下标落入“等于 pivot”的区间时，数组前 k 个位置已经由最小的 k 个元素占据，可以直接返回，无须继续排序。

为什么使用三路分区

普通二路分区在所有元素相等或存在大量重复值时，可能每次只能排除一个元素。例如数组全部是 1，如果基准值总被放到区间末尾，查找靠左的目标位置就会不断执行近乎完整的分区。

三路分区一次把所有等于基准值的元素集中到中间：

[ 小于 pivot | 等于 pivot | 大于 pivot ]
                 ↑
          [equalLeft, equalRight]

如果 k - 1 位于 [equalLeft, equalRight]，本轮就可以结束。这能显著改善重复元素较多时的表现。

示例推演

以如下输入为例：

arr = [1,3,5,7,2,4,6,8]
k = 4
target = k - 1 = 3

假设第一轮随机选到 6：

[1,3,5,2,4 | 6 | 8,7]
               ↑
          equalLeft = equalRight = 5

目标下标 3 < 5，所以第 4 小的数只可能在左侧，下一轮只处理下标 [0,4]。

假设第二轮选到 4：

[1,3,2 | 4 | 5]
           ↑
      equalLeft = equalRight = 3

目标下标正好落入等值区间，算法结束。此时数组前四项可能是：

[1,3,2,4]

它们内部没有排序，但确实是整个数组中最小的四个数。

JavaScript 实现

var smallestK = function (arr, k) {
    if (k <= 0) {
        return [];
    }
    if (k >= arr.length) {
        return arr.slice();
    }

    const partition = (left, right) => {
        const pivotIndex =
            left + Math.floor(Math.random() * (right - left + 1));
        const pivot = arr[pivotIndex];

        let less = left;
        let scan = left;
        let greater = right;

        while (scan <= greater) {
            if (arr[scan] < pivot) {
                [arr[less], arr[scan]] = [arr[scan], arr[less]];
                less++;
                scan++;
            } else if (arr[scan] > pivot) {
                [arr[scan], arr[greater]] = [arr[greater], arr[scan]];
                greater--;
            } else {
                scan++;
            }
        }

        return [less, greater];
    };

    const target = k - 1;
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const [equalLeft, equalRight] = partition(left, right);

        if (target < equalLeft) {
            right = equalLeft - 1;
        } else if (target > equalRight) {
            left = equalRight + 1;
        } else {
            return arr.slice(0, k);
        }
    }

    return arr.slice(0, k);
};

代码中的关键点

`target` 表示目标排名

const target = k - 1;

k - 1 是第 k 小元素在零下标数组中的目标位置，不是某一轮固定选择的基准位置。只有分区结果覆盖这个位置时，才能确定前 k 个元素已经就位。

与大于基准值的元素交换后不能立即移动`scan`

[arr[scan], arr[greater]] = [arr[greater], arr[scan]];
greater--;

从右侧交换到 scan 位置的元素还没有被检查，所以这里不能执行 scan++。

返回结果不保证有序

return arr.slice(0, k);

快速选择只保证前 k 个位置包含最小的 k 个元素，不保证它们从小到大排列。如果题目额外要求有序，可以对结果再排序。

实现会修改输入数组

分区过程通过交换元素原地修改 arr。如果调用方要求保留原数组，可以先复制：

const nums = arr.slice();

然后在 nums 上执行快速选择，但这会增加 O(n) 空间。

边界与陷阱

k === 0：应直接返回空数组，否则目标下标会变成 -1。
空数组：根据题目约束，此时 k 只能是 0。
k === arr.length：所有元素都是答案，直接返回数组副本。
重复元素：重复值不能去重，例如 [1,1,2]、k = 2 的答案应包含两个 1。
结果顺序：题目允许任意顺序，不要误以为快速选择会完成排序。
基准选择：固定选择区间端点容易在有序输入上退化，随机选择能降低持续出现极不均衡分区的概率。

复杂度分析

期望时间复杂度：O(n)。随机基准通常会让待处理区间快速缩小。
最坏时间复杂度：O(n²)。如果连续选到极端基准，每轮可能只排除很少的元素。
辅助空间复杂度：O(1)。实现使用循环和原地交换，没有递归调用栈。
返回数组空间：O(k)，来自 arr.slice(0, k)。

复杂度中的 O(1) 辅助空间不包含题目要求返回的结果数组。

ON THIS PAGE

#面试题 17.14. 最小 K 个数

#题目描述

#核心思路

#为什么使用三路分区

#示例推演

#JavaScript 实现

#代码中的关键点

#target 表示目标排名

#与大于基准值的元素交换后不能立即移动scan

#返回结果不保证有序

#实现会修改输入数组

#边界与陷阱

#复杂度分析